package  main.java.leetcode.editor.cn;
//2023-07-03 15:36:03
//请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(
//1)。 示例： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0);
// minStack.push(-3); minStack.getMin();   --> 返回 -3. minStack.pop(); minStack.
//top();      --> 返回 0. minStack.getMin();   --> 返回 -2. Related Topics 栈 设计 👍 91 👎 
//0

import java.util.ArrayDeque;
import java.util.Deque;

class MinStackLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        MinStack solution = new MinStackLcci().new MinStack();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class MinStack {

    Deque<Integer> stack;
    Deque<Integer> min_stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new ArrayDeque<>();
        min_stack = new ArrayDeque<>();
        min_stack.offerLast(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        if(x <= min_stack.peekLast()){
            min_stack.offerLast(x);
        }else {
            min_stack.offerLast(min_stack.peekLast());
        }
        stack.offerLast(x);
    }
    
    public void pop() {
        min_stack.pollLast();
        stack.pollLast();
    }
    
    public int top() {
        return stack.peekLast();
    }
    
    public int getMin() {
        return min_stack.peekLast();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
